#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>



char lookahead;
int num;
enum TERMINAL {
	ID,
	ADD,
	MUL,
	LBR,
	RBR,
	END,
	ERR

};
enum NON_TERMINAL {
	E,
	T,
	F
};

enum ACTION_TYPE {
	SHIFT,
	REDUCE,
	ERROR,
	ACC
};

#define NUM_TERMINAL  6
#define NUM_NONTERMINAL  3
#define NUM_STATES  12

struct action{
	enum ACTION_TYPE type;
	int id;
}  actionTable[NUM_STATES][NUM_TERMINAL];

int gotoTable[NUM_STATES][NUM_NONTERMINAL];
int stackPtr;
int stack[1024];
int value[1024];
void push(int state) {
	stack[stackPtr] = state;
	stackPtr ++;
}

void pop() {
	stackPtr --;
}

int top() {
	return stack[stackPtr - 1];
}

void valset(int offset, int v) {
	value[stackPtr - 1 + offset] = v;
}
int valget(int offset) {
	return value[stackPtr - 1 + offset];
}

void init() {
	int i, j;
	//stack
	stackPtr = 0;
	push(0);
	//action and goto tables
	for(i = 0; i < NUM_STATES; i ++) {
		for(j = 0; j < NUM_TERMINAL; j ++) {
		actionTable[i][j].type = ERROR;
		}
		for(j = 0; j < NUM_NONTERMINAL; j ++) {
		gotoTable[i][j] = -1;
		}
	}
                             
    gotoTable[0][E] = 1;
	gotoTable[0][T] = 2;
	gotoTable[0][F] = 3;
	gotoTable[4][E]=8;
	gotoTable[4][T]=2;
	gotoTable[4][F]=3;
	gotoTable[6][T]=9;
	gotoTable[6][F]=3;
	gotoTable[7][F]=10;

	
	//fill in the action table

	actionTable[2][ADD].type = REDUCE;
	actionTable[2][ADD].id = 2;
	actionTable[2][MUL].type = SHIFT;
	actionTable[2][MUL].id = 7;
	actionTable[2][RBR].type = REDUCE;
	actionTable[2][RBR].id = 2;
	actionTable[2][END].type = REDUCE;
	actionTable[2][END].id = 2;
	actionTable[0][ID].type=SHIFT;
	actionTable[0][ID].id=5;
	actionTable[0][LBR].type=SHIFT;
	actionTable[0][LBR].id=4;
	actionTable[1][ADD].type=SHIFT;
	actionTable[1][ADD].id=6;
    actionTable[1][END].type=ACC;
	actionTable[3][ADD].type=REDUCE;
	actionTable[3][ADD].id=4;
	actionTable[3][MUL].type=REDUCE;
	actionTable[3][MUL].id=4;
	actionTable[3][RBR].type=REDUCE;
	actionTable[3][RBR].id=4;
	actionTable[3][END].type=REDUCE;
	actionTable[3][END].id=4;
	actionTable[4][ID].type=SHIFT;
	actionTable[4][ID].id=5;
	actionTable[4][LBR].type=SHIFT;
	actionTable[4][LBR].id=4;
	actionTable[5][ADD].type=REDUCE;
	actionTable[5][ADD].id=6;
	actionTable[5][MUL].type=REDUCE;
	actionTable[5][MUL].id=6;
	actionTable[5][RBR].type=REDUCE;
	actionTable[5][RBR].id=6;
    actionTable[5][END].type=REDUCE;
	actionTable[5][END].id=6;
    actionTable[6][ID].type=SHIFT;
	actionTable[6][ID].id=5;
	actionTable[6][LBR].type=SHIFT;
	actionTable[6][LBR].id=4;
	actionTable[7][ID].type=SHIFT;
	actionTable[7][ID].id=5;
	actionTable[7][LBR].type=SHIFT;
	actionTable[7][LBR].id=4;
	actionTable[8][ADD].type=SHIFT;
	actionTable[8][ADD].id=6;
	actionTable[8][RBR].type=SHIFT;
	actionTable[8][RBR].id=11;
	actionTable[9][ADD].type=REDUCE;
	actionTable[9][ADD].id=1;
	actionTable[9][MUL].type=SHIFT;
	actionTable[9][MUL].id=7;
	actionTable[9][RBR].type=REDUCE;
	actionTable[9][RBR].id=1;
	actionTable[9][END].type=REDUCE;
	actionTable[9][END].id=1;
    actionTable[10][ADD].type=REDUCE;
	actionTable[10][ADD].id=3;
	actionTable[10][MUL].type=REDUCE;
	actionTable[10][MUL].id=3;
	actionTable[10][RBR].type=REDUCE;
	actionTable[10][RBR].id=3;
	actionTable[10][END].type=REDUCE;
	actionTable[10][END].id=3;
	actionTable[11][ADD].type=REDUCE;
	actionTable[11][ADD].id=5;
	actionTable[11][MUL].type=REDUCE;
	actionTable[11][MUL].id=5;
	actionTable[11][RBR].type=REDUCE;
	actionTable[11][RBR].id=5;
	actionTable[11][END].type=REDUCE;
	actionTable[11][END].id=5;
}



enum TERMINAL lexical(FILE *fp) {

	lookahead = getc(fp);

	while(lookahead == ' ' || lookahead == '\t' || lookahead == '\n') {
		lookahead = getc(fp);
	}
	if(isdigit(lookahead)) {
		num = 0;
		do {
			num = num * 10 + lookahead - '0';
			lookahead = getc(fp);
		} while(isdigit(lookahead)); 
		ungetc(lookahead, fp);
		return ID;
	} else if (lookahead == '+') {
		return ADD;
	} else if (lookahead == '*') {
		return MUL;
	} else if(lookahead == EOF) {
		return END;
	}else if(lookahead == '(') {
		return LBR;
	} else if(lookahead == ')') {
		return RBR;
	} else {
		return ERR;
	}
}



void parse(enum TERMINAL *input, int *number) {
	int currentState = 0;
	int currentValue = 0;
	int index = 0;
	int x=0;
	int i=0;
	
	while(1) {
		printf("currentState: %d\n", currentState);
		switch(actionTable[currentState][input[index]].type) {
			case SHIFT:
				currentValue = number[index];//store the current shifted value for further use
                                    				//how to shift
				currentState=actionTable[currentState][input[index]].id;
			    push(currentState);                          
			    index++; 
                                                                                                                         

				break;
			case REDUCE:
				switch(actionTable[currentState][input[index]].id) {
					case 1:
				        
						valset(-2,valget(0)+valget(-2));
						i=3;
						while(i>0)
						{
							pop();
							i--;
						}
						x=top();
						push(gotoTable[x][E]);
						currentState=gotoTable[x][E];
						
						//reduce by production 1
                                           
						break;

					case 2:
					    valset(0,valget(0));
						pop();
						x=top();
						push(gotoTable[x][E]);
						currentState=gotoTable[x][E];
						
						//reduce by production 2
						break;

					case 3:
					        
                        valset(-2,valget(0)*valget(-2));
						i=3;
						while(i>0)
						{
							pop();
							i--;
						}
						x=top();
						push(gotoTable[x][T]);
						currentState=gotoTable[x][T];
						
						//reduce by production 3

						break;

					case 4:

						//reduce by prod
					    valset(0,valget(0));
					    pop();
					    x=top();
						push(gotoTable[x][T]);
						currentState=gotoTable[x][T];
						
						break;

					case 5:

						//reduce by production 5
                        valset(-2,valget(-1));
						i=3;
						while(i>0)
						{
							pop();
							i--;
						}
						x=top();
						push(gotoTable[x][F]);
						currentState=gotoTable[x][F];
						
						break;

					case 6:

						//reduce by production 6
                        valset(0,currentValue);
						pop();
						x=top();
						push(gotoTable[x][F]);
						currentState=gotoTable[x][F];
						
						break;

					default:

						printf("ERROR REDUCE\n");

						exit(-1);

						break;

				}

				break;

			case ERROR:

				printf("ERROR ACTION\n");

				exit(-1);

				break;

			case ACC:

				if(input[index] == END) {

					printf("ACC\n");

					return;

				} else {

					printf("ERROR ACC\n");

					exit(-1);

				}

				break;

		}

	}

}





int main(int argc, char **argv) {

	enum TERMINAL input[1024]; 

	int number[1024];

	int inputIndex = 0;

	FILE *fp;

	enum TERMINAL temp;

	if(argc < 2) {

		printf("insufficient arguments");

		return 1;

	}

	fp = fopen(argv[1], "r");

	while((temp = lexical(fp)) != END) {

		input[inputIndex] = temp;

		number[inputIndex] = (temp == ID ? num : -1);

		inputIndex ++;

	}



	input[inputIndex] = END;

	fclose(fp);



	init();

	parse(input, number);

     printf("%d\n", valget(0));

	return 0;

}
